#include <queue>
using namespace std;

struct TreeNode
{
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

struct ListNode
{
    int val;
    ListNode *next;
    ListNode() : val(0), next(nullptr) {}
    ListNode(int x) : val(x), next(nullptr) {}
    ListNode(int x, ListNode *next) : val(x), next(next) {}
};

ListNode *getMedian(ListNode *left, ListNode *right)
{
    ListNode *slow = left;
    ListNode *fast = left;
    while (fast != right && fast->next != right)
    {
        fast = fast->next;
        fast = fast->next;
        slow = slow->next;
    }
    return slow;
}

TreeNode *buildTree(ListNode *left, ListNode *right)
{
    if (left == right)
        return nullptr;
    ListNode *mid = getMedian(left, right);
    TreeNode *root = new TreeNode(mid->val);
    root->left = buildTree(left, mid);
    root->right = buildTree(mid->next, right);
    return root;
}

TreeNode *sortedListToBST(ListNode *head)
{
    return buildTree(head, nullptr);
}
